package zhengqc.queue;

public class LoopDeque<E> implements Deque<E> {
    private E[] elementData;
    private int front;
    private int size;
    /* 循环队列默认容量大小 */
    private static final int DEFAULT_CAPACITY = 10;

    public LoopDeque(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        this.elementData = (E[]) (new Object[capacity+1]);
        this.front = 0;
        this.size = 0;
    }
    public LoopDeque() {
        this(DEFAULT_CAPACITY);
    }
    /* 将双端队列的索引映射到数组的索引 */
    public int convertIndex(int index) {
        return (this.front + index + elementData.length) % elementData.length;
    }
    /* 获取循环双端队列的容量 */
    private int getCapacity() {
        return elementData.length - 1;
    }
    /* 循环双端队列是否为已满 */
    private boolean isFull() {
        int rearIndex = convertIndex(this.size);
        if ((rearIndex +1) % elementData.length == front) {
            return true;
        }
        return false;
    }
    /* 动态调整循环双端队列容量 */
    private void adjustCapacity(int newCapacity) {
        E[] newElementData = (E[]) (new Object[newCapacity+1]);
        for (int i = 0; i < this.size; ++i) {
            newElementData[i] = this.elementData[(front+i)%elementData.length];
        }
        this.elementData = newElementData;
        front = 0;
    }
    @Override
    public int getSize() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public void frontEnqueue(E element) {
        if (isFull()) {
            adjustCapacity(2 * getCapacity());
        }
        this.front = convertIndex(-1);
        elementData[front] = element;
        ++ this.size;
    }

    @Override
    public E frontDequeue() {
        E oldElement = elementData[front];
        elementData[front] = null;
        front = convertIndex(1);
        -- this.size;
        int capacity = getCapacity();
        // 在保证循环队列缩容后的容量比默认容量大的情况下, 当循环队列的容量为数组元素的4倍以上, 则将循环队列的容量减半
        if (this.size <= (capacity >> 2) && (capacity >> 1) >= DEFAULT_CAPACITY) {
            adjustCapacity (elementData.length >> 1);
        }
        return oldElement;
    }

    @Override
    public void rearEnqueue(E element) {
        if (isFull()) {
            adjustCapacity(2 * getCapacity());
        }
        elementData[convertIndex(this.size)] = element;
        ++ this.size;
    }

    @Override
    public E rearDequeue() {
        int rearIndex = convertIndex(this.size-1);
        E oldElement = elementData[rearIndex];
        elementData[rearIndex] = null;
        -- this.size;
        int capacity = getCapacity();
        // 在保证循环队列缩容后的容量比默认容量大的情况下, 当循环队列的容量为数组元素的4倍以上, 则将循环队列的容量减半
        if (this.size <= (capacity >> 2) && (capacity >> 1) >= DEFAULT_CAPACITY) {
            adjustCapacity (elementData.length >> 1);
        }
        return oldElement;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("The Deque is empty!");
        }
        return elementData[front];
    }

    @Override
    public E getRear() {
        if (isEmpty()) {
            throw new IllegalArgumentException("The Deque is empty!");
        }
        return elementData[convertIndex(this.size-1)];
    }

    @Override
    public void clear() {
        for (int i = 0; i < elementData.length; ++i) {
            elementData[i] = null;
        }
        this.front = 0;
        this.size = 0;
    }

    @Override
    public String toString() {
        int rearIndex = convertIndex(this.size);
        StringBuilder sb = new StringBuilder();
        sb.append("LoopDeque: size=").append(size)
                .append(", capacity=").append(getCapacity())
                .append(", content={front->[");
        for (int i = this.front; i != rearIndex; i = (i+1)%elementData.length) {
            sb.append(elementData[i]);
            if ((i+1) % elementData.length != rearIndex) {
                sb.append(", ");
            }
        }
        sb.append("]<-rear}");
        return sb.toString();
    }
}
